﻿// 0812train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

/*
 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例1
输入: nums = [1,3,5,6], target = 5
输出: 2
 */
int solve01(vector<int>&nums, int target)
{
    int vec_size = nums.size();
    int left = 0;
    int right = vec_size - 1;

    while (left<=right)
    {
        int mid = left + (right - left) / 2;
        if (target==nums[mid])
        {
            return mid;
        }
        else if (target<nums[mid])
        {
            right = mid - 1;
        }
        else if (target>nums[mid])
        {
            left = mid + 1;
        }

    }

    //break前的最后一步，left==mid==right，假设都为0
	//如果此时target>mid，下一步left+1变为1，为插入位置
	//如果此时target<mid, 下一步right-1变为-1，left==0为插入位置
    return left;
    //solve01
}

/*
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1        
 */
int solve02(vector<int>&nums, int target)
{
    int vec_size = nums.size();
    int left = 0;
    int right = vec_size - 1;

    while (left<=right)
    {
        int mid = left + (right - left)/2;

        if (target==nums[mid])
        {
            return mid;
        }
        else if (target<nums[mid])
        {
            right = mid - 1;
        }
        else if (target>nums[mid])
        {
            left = mid + 1;
        }

    }

    return -1;
	//solve02------
}

int main()
{
    std::cout << "Hello World!\n";
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
